import java.util.Hashtable;
import java.util.Comparator;
public class Gogo
{
	public Gogo(){}
	
	 public static void main(String[] args)
	    {
	    	String[] str = {"0 2", "1 0", "2 0 1"};
	    	
	    	Gogo gogo = new Gogo();
	    	
	    	gogo.pageRank(str);
	    	
	    }
	 
	 private double[] rank;
	 Hashtable<String, Integer> hashedPages;

	
	public void pageRank(String[] s)           // s = {"page0 link link",..., "pageN link, link" }
	{
		String[] pages   = new String[s.length];
		
		int[] nLinks     = new int[s.length];
		
		EntryList[] rows =  new EntryList[s.length]; 
		
		for(int i = 0; i < rows.length; i++)
		{
			rows[i]= new EntryList();
		}

		hashedPages = new Hashtable<String, Integer>(Math.max(4*s.length/3+1, 16));
		
		for(int i = 0;  i < s.length; i++)             
		{
			String[] splited = s[i].split(" ");      //splited[0]     --> pageName
			                                         //splited[1...n] --> pageLinks     

			pages[i] = splited[0];
			
	        nLinks[i] = splited.length-1;
				
			hashedPages.put(pages[i], i); 
		}//for	
		
		for(int j = 0;  j < s.length; j++)     //j = index of the column
		{
			
			String[] splited = s[j].split(" ");
			
			for(int k = 1; k < splited.length; k++)   
			{
				double bbb = nLinks[j];
									
				double value = (1/bbb);
			
				Entry newEntry = new Entry(j, value);
				
				rows[hashedPages.get(splited[k])].add(newEntry);
				
				//System.out.println("Row " +hashedPages.get(splited[k]));
				//System.out.println("Column " +rows[hashedPages.get(splited[k])].tail.data.column);
				//System.out.println("Value " +rows[hashedPages.get(splited[k])].tail.data.value);

				
			}//for
			
		}//for
		
		rank = new double[s.length];
		
		for(int i = 0; i < rank.length; i++)
		{
			rank[i] = 1;
		}
		
		
	}//pageRank
	
    
	
	
	
	
	class myComparator implements Comparator<String>
	{
		public int compare(String a, String b)
		{
			int index_of_a = hashedPages.get(a);
			int index_of_b = hashedPages.get(b);
			
			if(rank[index_of_a] > rank[index_of_b])
			{
				return -1;
			}
			else if(rank[index_of_a] == rank[index_of_b])
			{
				return 0;
			}
			else
			    return 1;
		}
		
	}

    class BigMatrix 
	{
		public int nRows;      //The number of rows in this matrix 
		
		public int nCols;      //The number of columns in the matrix represented by this
		                       //object. That is, one more than the maximum of the 'col' 
		                       //entries in any of the nodes of a linked list representing
		                       //a row of the matrix. 
		public EntryList[] list; 
		
		
		
		
	    public BigMatrix(String[] newEntry)      //{"(1,1);(4,3);(5,8)", "(2,5);(3,4)", "(3,8);(4,5)"}
	    {
	    	/*nRows  = newEntry.length;
	    	
	    	String[] splited_on_semicolomns;
	    	
	        list = new EntryList[nRows];
	        
	        for(int i = 0; i < list.length; i++)
	        {
	        	list[i]= new EntryList();
	        }
	    	
	    	Entry create_entry;
	    	
	    	for(int i = 0, list_row = 0; i < newEntry.length && list_row < list.length; i++, list_row++) //length of the given string is 3
	    	{
	    		splited_on_semicolomns = newEntry[i].split(";");   //(1,1); (4,3); (5,8)
	    		
	    			
	    			for(int j = 0; j < splited_on_semicolomns.length; j++)
	    			{
	    				create_entry = new Entry(splited_on_semicolomns[j]);  
	    				 
	    				list[list_row].add(create_entry);
	        				     
	        		}
	    			 
	    			if(list[list_row].tail.data.column > nCols)
					  {
						  nCols = list[list_row].tail.data.column+1;
					  }	    		
	    	}*/
	    }//constructor
	    
	    
	    public double[] multiply(int[] x)
	    {
	    	double[] result = new double[nRows];
	    	
	    	for(int i = 0; i < list.length; i++)
	    	{
	    	   for(EntryList marker = list[i].head; marker != null; marker = marker.next)
	    	   {
	    		   result[i] += x[marker.data.column] * marker.data.value;
	    	   }
	    	   System.out.println(result[i]);
	    	   
	    	}
	    	
	    	
	    	return result;
	    }

	}//BigMatrix    
	   

class EntryList 
//class represents a row of entry
{
		Entry data;       //The nodes of an EntryList are of type Entry 
	   
		EntryList next;
	    EntryList head;
	    EntryList tail;   /*points to the last node in the list. This is 
	                        useful only for lists whose first element is
	                        never going to be removed, but that is the case
	                        in the BigMatrix application. See the add method
	                        and the BigMatrixHints.html for further information
	                        about how this field is used. */
	   EntryList()
	    {
	    	data = null;
	    	next = null;
	    }
	    
	   
	    /**void add(Entry x)
	     * Adds a new node containing x at the tail. To add a new item to the list
	     * x, just go immediately to x.tail, which will be the last item in the
	     * list, and set the next of that item to a new EntryList, and fill in that
	     * new node appropriately, and then, finally, update x.tail to point to this
	     * new last item. There is more explanation in the BigMatrixHints.html file. 
	     * @param x
	     */
	    void add(Entry x)
	    {
	       EntryList newEntry = new EntryList();
	       newEntry.data = x;   //next = null;
	       
	       if(tail == null)
	       {
	    	  head = newEntry;
	     	  tail = newEntry;
	     	  newEntry.next = null;
	       }
	       else
	    	   tail.next= newEntry;
	           tail = newEntry;
	           
	       }
}//class EntryList


       class Entry
       {
		  int    column;
		  double value;
		
		  public Entry(int col, double val)   //(n,m)
		  {
			column = col;
			value = val;
		  }		

       }

}//class Google

